package leetcode_周赛._2023._11;

/**
 * 第 372 场周赛
 * AC_2
 *
 * @author yezh
 * @date 2023/11/19 14:19
 */
public class _19 {

    /**
     * 2939. 最大异或乘积
     * 算法: 位运算
     * <p/>
     * 将 a, b 同为 0 的比特位变为 1 后, a ^ b 中 1 的个数不变
     * ax = a ^ x, bx = b ^ x, ax + bx 是一个定值
     * ax * bx 的值要最大, 则 ax 要等于 bx
     * 所以, 要让 ax 和 bx 尽可能地相等
     * <p>
     * 因为 x < 2 ^ n, 所以 x 最多有 n 个 1
     * <p>
     * 只需要讨论 a, b 后 n 位中, a 和 b 的同一个比特位一个是 1 另一个是 0 的情况。
     * x 中的 1 要怎么分
     * 1、如果 a > b, 则把所有 1 分给 b
     * 2、如果 a = b, 则把 x 中的高位 1 分给 a, 高位后的 1 分给 b
     */
    public int maximumXorProduct(long a, long b, int n) {
        // 保证 a >= b
        if (a < b) {
            long tmp = a;
            a = b;
            b = tmp;
        }
        long mask = (1L << n) - 1;
        // 第 n 位及其左边, 无法被 x 影响, 先算
        long ax = a & ~mask;
        long bx = b & ~mask;
        // 低于 n 位能被 x 影响
        a &= mask;
        b &= mask;

        // 需要分配, a XOR x, b XOR x 一个是 0, 另一个是 1 的情况
        long left = a ^ b;
        // 无需分配
        long one = left ^ mask;
        // 先加到异或结果中
        ax |= one;
        bx |= one;

        // 把 left 分配到 ax、bx 中
        if (left > 0 && ax == bx) {
            // 尽量均匀分配，例如把 1111 分成 1000 和 0111
            long highBit = 1L << (63 - Long.numberOfLeadingZeros(left));
            ax |= highBit;
            left ^= highBit;
        }
        // 如果 a & ~mask 更大，则应当全部分给 bx（注意最上面保证了 a>=b）
        bx |= left;

        long mod = 1_000_000_007;
        return (int) (ax % mod * (bx % mod) % mod);
    }

}
